/*
 * @Author: _LJP 2634716776@qq.com
 * @Date: 2023-12-25 16:50:22
 * @LastEditors: _LJP 2634716776@qq.com
 * @LastEditTime: 2024-01-02 15:17:22
 * @FilePath: /my_-linux/Pro24/AVL/AVLTree/AVLTree.hpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */

#pragma once

#include<iostream>

#include<assert.h>

namespace MyAVL{
    /*
     * AVL树又被称为平衡搜索二叉树,全名为高度平衡搜索二叉树
     * 其节点与节点之间的高度差不超过1;
     * 由于树的特殊结构导致节点之间的高度差不能相同;
     * 且节点与节点采用三叉链接的形式进行连接,意味着需要三个指针进行连接:
     * _left  _right   _parent 三个指针;
     * 节点内数据的保存使用 pair<K,V> 的数据结构进行保存;
     */

    template<class K,class V>
    struct AVLTreeNode{
        AVLTreeNode(const std::pair<K,V> &kv)
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_kv(kv) 
        ,_bf(0)
        {}

        AVLTreeNode<K, V> *_left;
        AVLTreeNode<K, V> *_right;
        AVLTreeNode<K, V> *_parent; //三叉链
        std::pair<K,V> _kv;
        int _bf;    //balance factor 平衡因子

        /*
         * 平衡因子为右子树高度减去左子树高度
         * 利用平衡因子来判断该树是否平衡,是否需要进行旋转
         */
    };

    template<class K,class V>
    class AVLTree{
        typedef AVLTreeNode<K,V> Node;
        public:

            bool Insert(const std::pair<K,V>& kv){

                if (_root == nullptr)
                {
                    _root = new Node(kv);
                    return true;
                }

                Node *parent = nullptr;
                Node *cur = _root;
                while (cur)
                {
                    if (cur->_kv.first < kv.first)
                    {
                        parent = cur;
                        cur = cur->_right;
                    }
                    else if (cur->_kv.first > kv.first)
                    {
                        parent = cur;
                        cur = cur->_left;
                    }
                    else
                    {
                        return false;
                    }
                }

                cur = new Node(kv);
                if (parent->_kv.first < kv.first)
                {
                    parent->_right = cur;
                }
                else
                {
                    parent->_left = cur;
                }

                cur->_parent = parent;

                // ... 控制平衡
                // 更新平衡因子
                while (parent)
                {
                    if (cur == parent->_left)
                    {
                        parent->_bf--;
                    }
                    else // if (cur == parent->_right)
                    {
                        parent->_bf++;
                    }

                    if (parent->_bf == 0)
                    {
                        // 更新结束
                        break;
                    }
                    else if (parent->_bf == 1 || parent->_bf == -1)
                    {
                        // 继续往上更新
                        cur = parent;
                        parent = parent->_parent;
                    }
                    else if (parent->_bf == 2 || parent->_bf == -2)
                    {
                        // 子树不平衡了，需要旋转
                        if (parent->_bf == 2 && cur->_bf == 1)
                        {
                            RotateL(parent);
                        }
                        else if (parent->_bf == -2 && cur->_bf == -1)
                        {
                            RotateR(parent);
                        }
                        else if (parent->_bf == 2 && cur->_bf == -1)
                        {
                            RotateRL(parent);
                        }
                        else if (parent->_bf == -2 && cur->_bf == 1)
                        {
                            RotateLR(parent);
                        }

                        break;
                    }
                    else
                    {
                        assert(false);
                    }
                }

                return true;
            }

            void InOrder()
            {
                _InOrder(_root);
            }

            bool IsBalance(){
                return _IsBalance(_root);
            }

        protected:
            void RotateL( Node* parent ){
                /*  左单旋操作
                 *              x
                 *            /   \
                 *         a(h)    y
                 *               /   \
                 *             b(h) c(h+1)
                 * 如该演示为例,其中a子树与b子树的高度为h,c子树的高度为h+1;
                 * 此时平衡因子中y节点的平衡因子为1,x节点的平衡因子由1变为2不平衡,需要进行左旋操作
                 * 
                 * 假设该处的abc子树都为1个节点时(c节点还拥有一个左或右的子节点)左旋操作为:
                 * y节点的左子树变为x节点的右子树,y的左子树变为x节点;
                 */

                // 设置好需要移动(操作)的指针
                Node *cur = parent->_right;
                Node *curleft = cur->_left;

                parent->_right = curleft;
                if (curleft)
                {
                    curleft->_parent = parent;
                }

                cur->_left = parent;

                Node *ppnode = parent->_parent;

                parent->_parent = cur;

                if (parent == _root)
                {
                    _root = cur;
                    cur->_parent = nullptr;
                }
                else
                {
                    if (ppnode->_left == parent)
                    {
                        ppnode->_left = cur;
                    }
                    else
                    {
                        ppnode->_right = cur;
                    }

                    cur->_parent = ppnode;
                }

                parent->_bf = cur->_bf = 0;
            }

            void RotateR(Node *parent)
            {
                /*  右单旋操作
                 *              x
                 *            /   \
                 *           y    a(h)
                 *         /    \
                 *      b(h+1) c(h)
                 * 如该演示为例,其中a子树与c子树的高度为h,b子树的高度为h+1;
                 * 此时平衡因子中y节点的平衡因子为-1,x节点的平衡因子由-1变为-2不平衡,需要进行右旋操作
                 *
                 * 假设该处的abc子树都为1个节点时(b节点还拥有一个左或右的子节点)右旋操作为:
                 * y节点的右子树变为x节点的左子树,y的右子树变为x节点;
                 */
                
                
                //右旋操作与左旋操作相当
                Node *cur = parent->_left;
                Node *curright = cur->_right;

                parent->_left = curright;
                if (curright)
                    curright->_parent = parent;

                Node *ppnode = parent->_parent;
                cur->_right = parent;
                parent->_parent = cur;

                if (ppnode == nullptr)
                {
                    _root = cur;
                    cur->_parent = nullptr;
                }
                else
                {
                    if (ppnode->_left == parent)
                    {
                        ppnode->_left = cur;
                    }
                    else
                    {
                        ppnode->_right = cur;
                    }

                    cur->_parent = ppnode;
                }

                parent->_bf = cur->_bf = 0;
            }

            void RotateLR(Node* parent){
                /*
                 * 左右双旋操作:
                 * 左右双旋操作一般为parent节点的平衡因子为 -2
                 * parent节点的左子树节点subL的平衡因子为1;
                 * subL节点的右子树节点subLR的平衡因子为-1或1时触发;
                 * 在进行左右双旋操作时直接调用左单旋与右单旋操作即可;
                 * 
                 * 调用结束后应该注意更新整棵树的平衡因子
                 */

                Node* subL = parent->_left;
                Node* subLR = subL->_right;
                
                int bf = subLR->_bf;
                // 画图相结合 -> 利用subLR->_bf判断所插入的节点是左子树还是右子树
                // 根据结果来确定如何更新平衡因子

                RotateL(parent->_left);
                RotateR(parent);

                if(bf == 0){
                    parent->_bf = 0;
                    subL->_bf=0;
                    subLR->_bf=0;
                }
                else if(bf == -1){
                    parent->_bf = 1;
                    subLR->_bf = 0;
                    subL->_bf = 0;
                }
                else if (bf == 1)
                {
                   parent->_bf = 0;
                   subL->_bf = -1;
                   subLR->_bf = 0;
                }
                else{// 避免AVL树的平衡因子出现较大问题 当出现较大问题时可以直接断言结束进程
                    assert(false);
                }
            }

            void RotateRL(Node*parent){

                Node *cur = parent->_right;
                Node *curleft = cur->_left;
                int bf = curleft->_bf;

                RotateR(parent->_right);
                RotateL(parent);

                if (bf == 0)
                {
                    cur->_bf = 0;
                    curleft->_bf = 0;
                    parent->_bf = 0;
                }
                else if (bf == 1)
                {
                    cur->_bf = 0;
                    curleft->_bf = 0;
                    parent->_bf = -1;
                }
                else if (bf == -1)
                {
                    cur->_bf = 1;
                    curleft->_bf = 0;
                    parent->_bf = 0;
                }
                else
                {
                    assert(false);
                }
            }

            void _InOrder(const Node* root){
                if(root == nullptr)
                    return;
                
                _InOrder(root->_left);
                        
                std::cout << root->_kv.first << " : " << root->_kv.second << std::endl;
                
                _InOrder(root->_right);
            }

            int GetHeight(Node* root){
                if(root == nullptr){
                    return 0;
                }

                int leftH = GetHeight(root->_left);
                int rightH = GetHeight(root->_right);

                return leftH > rightH ? leftH+1 : rightH+1;
            }

            bool _IsBalance(Node* root){
                if(root == nullptr){
                    return true;
                }

                int leftH = GetHeight(root->_left);
                int rightH = GetHeight(root->_right);

                if(rightH-leftH != root->_bf){
                    std::cout<<root->_kv.first<<"节点平衡因子异常"<<" ";
                }

                return abs(leftH-rightH)<2 
                && _IsBalance(root->_left)
                && _IsBalance(root->_right);
            }

        private:
            Node* _root=nullptr;

        public:
            int _rotateCount = 0;
    };
}